# -*- coding:utf-8 -*-

# 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合
# 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母
# 示例:
# 输入："23"
# 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

# 一遍通过
# 当然这道题也可以使用递归来做，但是感觉如果能用循环做到就没必要使用递归来做了
class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if len(digits)==0:
            return [];

        digit_match_chars = [[], [], ['a','b','c'], ['d','e','f'], ['g','h','i'],
                        ['j','k','l'], ['m','n','o'], ['p','q','r','s'], ['t','u','v'], ['w','x','y','z']];
        rtn = [""];
        for i in xrange(0, len(digits)):
            chars = digit_match_chars[int(digits[i])];
            temp = [];
            for j in xrange(0, len(rtn)):
                for k in xrange(0, len(chars)):
                    temp.append(rtn[j] + chars[k]);
            rtn = temp;
        return rtn;


t = Solution();
print t.letterCombinations("");